1. References
The following U.S. patents and papers provide useful background information, for which they are incorporated herein by reference in their entirety.                a) Patents        
6,349,088Febuary 2002Ginzboorg, et al.6,286,052September 2001McCloghrie, et al.6,247,061June 2001Douceur, et al.6,167,027December 2000Aubert, et al.6,118,791September 2000Fichou, et al.5,625,622April 1997Johri5,339,332August 1994Kammerl
2. Introduction
Presently, networks that use Internet Protocol (IP) have physical properties that allow traffic transmission rates that are beyond the needs of the users of the network. As a result, either users pay for bandwidth and end up using only a fraction of the bandwidth that they paid for, or they take advantage of excess bandwidth and use bandwidth at rates beyond what they actually paid for. To overcome this and to charge users only for bandwidth rate that they actually utilize, Internet service providers (ISPs) limit the transmission rate by manipulating the physical connection capabilities.
Networks using IP usually communicate using transmission control protocol (TCP) or user datagram protocol (UDP). These protocols do not provide mechanisms for controlling the rate of individual flows. Therefore, in order to control the aggregate rate of individual flows, a method to perform asynchronous centralized control of non-cooperative process flows is required. Data packets are classified into process flows, or flows, based on an analysis of various characteristics of the data packet and/or the data contained in the packet header. For example, if the data packet contains a packet header, the packet may be classified as a first type of data packet if the source IP address falls within a first range of source IP addresses, the destination IP address falls within a first range of destination IP addresses, the protocol data falls within a first range of protocol data values, the source port data falls within a first range of source port data values, and the destination port data falls within a first range of destination port data values. Similarly the data packet may be classified as belonging to a second flow if the source IP address falls within a second range of source IP addresses. Non-cooperative process flows are unrelated flows.
A conventional method used to perform asynchronous centralized control of non-cooperative flows is the two-buckets-three-colors or single rate three color marker (TCM) algorithm. Reference is now made to FIG. 1A, which illustrates the operation of the TCM algorithm. TCM uses two buckets 100 and 110. Packets inserted into bucket 100 are considered to be colored in green, while packets inserted into bucket 110 are considered to be colored in yellow. Packets that are not inserted into either bucket 100 or bucket 110 are considered to be colored in red. Buckets 100 and 110 usually contain a different number of tokens. The number of tokens in bucket 100 is equal to the committed burst size (CBS) (or commit rate), while the number of tokens in bucket 110 is equal to the excess burst size (EBS) (or excess rate). The tokens for buckets 100 and 110 are generated at a combined rate called committed information rate (CIR). Tokens are added to bucket 110 when bucket 100 is full. An arriving packet is inserted into bucket 100, if the number of tokens in bucket 100 is greater than the number of tokens necessary for the arriving packet. If the arriving packet was inserted into bucket 100, the algorithm drops tokens from bucket 100. The number of dropped tokens is equal to the number of tokens consumed by the packet. As illustrated in FIG. 1B, in case of overflow, i.e., all the tokens in bucket 100 have been used, the packet is forwarded to bucket 110. As illustrated in FIG. 1C, if there is an overflow from bucket 110 as well as from bucket 100, the packet is considered to be colored in red. Green packets are transmitted at a rate equal to the CBS, yellow packets are transmitted at a rate equal to the EBS, and red packets are not transmitted.
Different algorithms based on the principle described in the TCM algorithm may be found in discussions relating to conventional techniques. For example, leaky bucket, adaptive leaky bucket, one bucket two colors, are just a few of the conventional techniques.
TCM and other algorithms generally do not share the rate evenly between different flows. The flow rate depends on factors that are outside the control of the algorithm, and therefore the outcome is not necessarily desirable. Another major disadvantage of these conventional algorithms is the fact that they cannot discern the flow rates according to flow types. For example, if the TCM algorithm accepts both a voice over IP (VoIP) flow and a file transport protocol (FTP) flow, both packets would be handled identically. Because FTP over TCP is greedy it will consume more bandwidth. This will affect VoIP flow transmission. However, it would be more desirable to give the VoIP flow its requested flow rate since it is sensitive to rate disturbances, and give the FTP whatever bandwidth that remains. But, the conventional TCM algorithm does not provide for such an allocation of bandwidth.
Therefore, it would be advantageous to have a method that dynamically applies fair rate constraints to different flows according to the flows' types and the flows' real-time bandwidth demands.